package com.yoshino.leetcode.improve40.sixth;

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int differ = 0;
        int[] cur = new int[128];
        // 没有出现则为0，后续为负数的都是过载的
        for (char c : t.toCharArray()) {
            if (++cur[c] == 1) {
                differ++;
            }
        }
        int left = 0, right = 0, j = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (--cur[c] == 0) {
                differ--;
            }
            if (differ == 0) {
                while (cur[s.charAt(j)] < 0) {
                    ++cur[s.charAt(j++)];
                }
                if (left == right || right - left > i - j + 1) {
                    // 初次 或者  短
                    left = j;
                    right = i + 1;
                }
            }
        }
        return s.substring(left, right);
    }

    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            // 找到左右两边有效的值
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }

    public boolean validPalindrome(String s) {
        // 找到不是回文的，再去掉左边或者右边的再判断
        int left = 0, right = s.length() - 1;
        while (left < right && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }
        return reverse(left + 1, right, s) || reverse(left, right - 1, s);
    }
    private boolean reverse(int left, int right, String s) {
        while (left < right && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }
        return right <= left;
    }

    public int countSubstrings(String s) {
        int n = s.length(), res = 0;
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (chars[i] == chars[j] && (i - j < 3 || dp[j + 1][i - 1])) {
                    dp[j][i] = true;
                    res++;
                }
            }
        }
        return res;
    }
}